package _interview75;

import java.util.*;

/**
 * 2462. 雇佣 K 位工人的总代价
 */
public class No2462 {
    public long totalCost(int[] costs, int k, int candidates) {
        Deque<Integer> list = new ArrayDeque<>();
        for (int cost : costs) list.add(cost);

        PriorityQueue<Integer> leftHeap = new PriorityQueue<>();
        PriorityQueue<Integer> rightHeap = new PriorityQueue<>();
        for (int i = 0; i < candidates && !list.isEmpty(); i++) {
            leftHeap.add(list.pollFirst());
            if (!list.isEmpty()) rightHeap.add(list.pollLast());
        }

        long ans = 0;
        for (int i = 0; i < k; i++) {
            if (rightHeap.isEmpty() || (!leftHeap.isEmpty() && leftHeap.peek() <= rightHeap.peek())) {
                ans += leftHeap.poll();
                if (!list.isEmpty()) leftHeap.offer(list.pollFirst());
            } else {
                ans += rightHeap.poll();
                if (!list.isEmpty()) rightHeap.offer(list.pollLast());
            }
        }
        return ans;
    }
}
